#include <bits/stdc++.h>
using namespace std;

/*
1352. 最后 K 个数的乘积
已解答
中等
相关标签
相关企业
提示
设计一个算法，该算法接受一个整数流并检索该流中最后 k 个整数的乘积。

实现 ProductOfNumbers 类：

ProductOfNumbers() 用一个空的流初始化对象。
void add(int num) 将数字 num 添加到当前数字列表的最后面。
int getProduct(int k) 返回当前数字列表中，最后 k 个数字的乘积。你可以假设当前列表中始终 至少 包含 k 个数字。
题目数据保证：任何时候，任一连续数字序列的乘积都在 32 位整数范围内，不会溢出。

 

示例：

输入：
["ProductOfNumbers","add","add","add","add","add","getProduct","getProduct","getProduct","add","getProduct"]
[[],[3],[0],[2],[5],[4],[2],[3],[4],[8],[2]]

输出：
[null,null,null,null,null,null,20,40,0,null,32]

解释：
ProductOfNumbers productOfNumbers = new ProductOfNumbers();
productOfNumbers.add(3);        // [3]
productOfNumbers.add(0);        // [3,0]
productOfNumbers.add(2);        // [3,0,2]
productOfNumbers.add(5);        // [3,0,2,5]
productOfNumbers.add(4);        // [3,0,2,5,4]
productOfNumbers.getProduct(2); // 返回 20 。最后 2 个数字的乘积是 5 * 4 = 20
productOfNumbers.getProduct(3); // 返回 40 。最后 3 个数字的乘积是 2 * 5 * 4 = 40
productOfNumbers.getProduct(4); // 返回  0 。最后 4 个数字的乘积是 0 * 2 * 5 * 4 = 0
productOfNumbers.add(8);        // [3,0,2,5,4,8]
productOfNumbers.getProduct(2); // 返回 32 。最后 2 个数字的乘积是 4 * 8 = 32 
 

提示：

0 <= num <= 100
1 <= k <= 4 * 104
add 和 getProduct 最多被调用 4 * 104 次。
在任何时间点流的乘积都在 32 位整数范围内。
*/

// 法一
class ProductOfNumbers {
	public:
	ProductOfNumbers() {
		prefix.push_back(1);
		n = 0;
	}

	void add(int num) {
		n++;
		if (num == 0) {
			zeros.push_back(n - 1); // 当前索引
			prefix.clear();
			prefix.push_back(1); // 重置
		} else {
			prefix.push_back(prefix.back() * num);
		}
	}

	int getProduct(int k) {
		int left = n - k;
		int right = n - 1;
		// 二分
		auto it = lower_bound(zeros.begin(), zeros.end(), left);
		if (it != zeros.end() && *it <= right) {
			return 0;
		}
		// 计算乘积
		int m = prefix.size();
		return prefix.back() / prefix[m - 1 - k];
	}

private:
	vector<int> prefix;
	vector<int> zeros;
	int n;
};

/**
 * Your ProductOfNumbers object will be instantiated and called as such:
 * ProductOfNumbers* obj = new ProductOfNumbers();
 * obj->add(num);
 * int param_2 = obj->getProduct(k);
 */

 // 法二
 
class ProductOfNumbers
{
    vector<int> li;
public:
    ProductOfNumbers()
    {
        li.push_back(1);
    }

    void add(int num)
    {
        if (num == 0)
        {
            li.clear();
            li.push_back(1);
            return;
        }
        if (li.empty())
        {
            li.push_back(num);
        }
        else
        {

            li.push_back(num * li.back());
        }
    }

    int getProduct(int k)
    {
        if (li.size() <= k)
        {
            return 0;
        }
        return li.back() / *(li.end() - k-1);
    }
};

/**
 * Your ProductOfNumbers object will be instantiated and called as such:
 * ProductOfNumbers* obj = new ProductOfNumbers();
 * obj->add(num);
 * int param_2 = obj->getProduct(k);
 */